# LeetCode 509、斐波那契数
# 一、题目描述
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例 1：
**输入：**n = 2 **输出：**1 **解释：**F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
**输入：**n = 3 **输出：**2 **解释：**F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
**输入：**n = 4 **输出：**3 **解释：**F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
0 <= n <= 30
# 二、题目解析
# 三、参考代码
# Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 斐波那契数（LeetCode 509）：https://leetcode.cn/problems/fibonacci-number/
class Solution {
int times1;
public int fib(int N) {
times1 = 0;
int result = myFib1(N);
return result ;
}
private int myFib1( int N){
times1++;
if ( N == 0 ) return 0 ;
if ( N == 1 ) return 1 ;
return myFib1( N - 1 ) + myFib1( N - 2);
}
}
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 斐波那契数（LeetCode 509）：https://leetcode.cn/problems/fibonacci-number/
class Solution {
int times1;
int[] memo;
public int fib(int N) {
times1 = 0;
memo = new int[ N + 1 ];
Arrays.fill(memo, -1);
int result = myFib2(N);
System.out.println("myFib2 调用的次数为 ： " + times1 );
return result ;
}
// 记忆化搜索
// 在递归的基础上增加了一个记忆的功能，依旧是自上向下的解决问题
// 相当于数组从后向前挖坑，挖到最前面在开始填坑
private int myFib2( int N){
times1++;
if ( N == 0 ) return 0 ;
if ( N == 1 ) return 1 ;
if ( memo[N] == -1) {
memo[N] = myFib2( N - 1 ) + myFib2( N - 2);
}
return memo[N];
}
}
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 斐波那契数（LeetCode 509）：https://leetcode.cn/problems/fibonacci-number/
class Solution {
int times1;
int[] memo;
public int fib(int N) {
times1 = 0;
memo = new int[ N + 1 ];
Arrays.fill(memo, -1);
int result = myFib3(N);
System.out.println("myFib3 调用的次数为 ： " + times1 );
return result ;
}
// 动态规划：自下向上的解决问题
// 相当于结果数组从前往后进行填充，一个萝卜一个坑
private int myFib3( int N){
if ( N < 2) return N;
// 1、确定 dp 数组的含义
// 即 dp[n] 表示当 n 时是xxxx
int[] dp = new int[ N + 1];
// 3、确定 dp 初始状态
// 初始化默认值、前面几个状态的值
Arrays.fill(dp,-1);
dp[0] = 0;
dp[1] = 1;
for(int i = 2 ; i <= N ; i++){
// 2、寻找 dp 数组元素之间的联系
// 即 dp[i] 的状态可以怎么样通过前面的状态获取到
dp[i] = dp[i-1] + dp[i-2];
}
return dp[N];
}
}
# Python代码
class Solution:
def __init__(self):
self.times1 = 0
def fib(self, N):
self.times1 = 0
result = self.myFib1(N)
print(self.times1)
return result
def myFib1(self, N):
self.times1 += 1
if N == 0:
return 0
if N == 1:
return 1
return self.myFib1(N - 1) + self.myFib1(N - 2)
# 记忆化搜索
class Solution:
def __init__(self):
self.times1 = 0
self.memo = None
def fib(self, N):
self.times1 = 0
self.memo = [-1] * (N + 1)
result = self.myFib2(N)
print("myFib2 调用的次数为: ", self.times1)
return result
def myFib2(self, N):
self.times1 += 1
if N == 0:
return 0
if N == 1:
return 1
if self.memo[N] == -1:
self.memo[N] = self.myFib2(N - 1) + self.myFib2(N - 2)
return self.memo[N]
# 动态规划
class Solution:
def __init__(self):
self.times1 = 0
self.memo = None
def fib(self, N):
self.times1 = 0
self.memo = [-1] * (N + 1)
result = self.myFib3(N)
print("myFib3 调用的次数为: ", self.times1)
return result
def myFib3(self, N):
if N < 2:
return N
dp = [-1] * (N + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, N + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[N]